连续子数组的最大和： https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?
//方法一
class Solution {
  public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        //经典且高频dp问题
        //定义状态# f(i): 以i下标结尾的最大连续子序列的和
        //状态递推：f(i) = max(f(i-1)+array[i], array[i]) 【这里一定要注意连续关键字】
        //状态初始化：f(0) = array[0], max = array[0]
        int max_value = array[0];
        int* dp = new int[array.size()];
        dp[0] = array[0];
        for (int i = 1; i < array.size(); i++) 
        {
            dp[i] = max(dp[i - 1] + array[i], array[i]);
            if (max_value < dp[i]) 
            {
                max_value = dp[i];
            }
        }
        delete dp;
        return max_value;
    }
};
//方法二
//很明显，上面的代码，只会使用dp[i] 和 dp[i-1]，所以是有优化的可能的
class Solution {
  public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        //经典且高频dp问题
        //定义状态# f(i): 以i下标结尾的最大连续子序列的和
        int max_value = array[0];
        int total = array[0]; //当前累计的和
        //for 循环，用来检测以i下标结尾的连续子序列的和
        for (int i = 1; i < array.size(); i++) 
        {
            if (total >= 0) 
            {
                //如果之前total累计的和>=0,说明当前数据+total，有利于整体增大
                total += array[i];
            } 
            else 
            {
                //如果之前累计的和<0,说明当前数据+total，不利于整体增大,丢弃之前的所有值
                //这里有一个基本事实，就是之前的连续数据和是确定的。
                //连续，是可以从以前到现在，也可以是从现在到以后。至于要不要加以前，就看以前对整体增大又没有
                贡献度
                total = array[i];
            }
            //走到这，标示以i下标结尾的最大连续子序列的和已经算出，进行最大值统计
            if (max_value < total) 
            {
                max_value = total;
            }
        }
        return max_value;
        
    }
};
